package com.algorithm;


import java.util.Queue;
import java.util.Random;

/*
    快速排序的递归算法
 */
public class FastSort {

    public static void main(String[] args){
        int[] input = new int[]{7,1,8,4,8,5,2,7};
        QuickSort(input,0,input.length-1);
        for(int a :input){
            System.out.print(a+" ");
        }
    }

    //找出基准数在排序后固定的下标位置，并且在基准数左边都比基准数小，右边都比基准数大
    public static int Partition(int data[],int start,int end){
        int temp = data[start];
        while(start < end){
            while(start < end && data[end] >= temp){    //需要交换
                end--;  // 找到需要交换的
            }
            data[start] = data[end];    // 交换
            while(start < end && data[start] <= temp){
                start++;
            }
            data[end] = data[start];
        }
        data[start] = temp;
        return start;   // 当前划分位置，并按这个位置进行子序列划分
    }

    public static void QuickSort(int[] data,int start,int end){
        if(start < end){
            int temp = Partition(data,start,end);
            QuickSort(data,start,temp-1);
            QuickSort(data,temp+1,end);
        }
    }

}
